#define _CRT_SECURE_NO_WARNINGS 1
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//#include <cstddef>
//#include <cstdlib>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        ListNode* ghead, * gtail, * lhead, * ltail;
//        ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        struct ListNode* cur = pHead;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                ltail->next = cur;
//                ltail = ltail->next;
//            }
//            else
//            {
//                gtail->next = cur;
//                gtail = gtail->next;
//            }
//            cur = cur->next;
//        }
//        ltail->next = ghead->next;
//        gtail->next = NULL;
//        struct ListNode* head = lhead->next;
//        free(ghead);
//        free(lhead);
//        return head;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* curA = headA;
//    struct ListNode* curB = headB;
//    int lenA = 1;
//    int lenB = 1;
//    while (curA)
//    {
//        curA = curA->next;
//        lenA++;
//    }
//    while (curB)
//    {
//        curB = curB->next;
//        lenB++;
//    }
//    if (curA != curB)
//        return NULL;
//    int gap = abs(lenA - lenB);
//    struct ListNode* longList = headA, * shortList = headB;
//    if (lenA < lenB)
//    {
//        longList = headB;
//        shortList = headA;
//    }
//    while (gap--)
//    {
//        longList = longList->next;
//    }
//    while (longList != shortList)
//    {
//        longList = longList->next;
//        shortList = shortList->next;
//    }
//    return longList;
//}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (slow == fast)
//            return true;
//    }
//    return false;
//}